package linklist;

/**
 * @author "随风Coding"
 * @email 1431471764@qq.com
 * @date 2025/8/13 06:38
 */
public class ReverseLinkedLists {

    // 链表节点定义（静态内部类）
    public static class ListNode {
        int val;         // 节点存储的值
        ListNode next;   // 指向下一个节点的指针

        // 无参构造（用于灵活创建节点）
        ListNode() {
        }

        // 带值构造（常用）
        ListNode(int val) {
            this.val = val;
        }

        // 带值和下一个节点的构造（可选）
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 双指针法（迭代）反转链表
     *
     * @param head 原链表头节点
     * @return 反转后的新链表头节点
     */
    public static ListNode doublePoint(ListNode head) {
        ListNode pre = null;   // 前驱节点（初始为 null）
        ListNode current = head; // 当前节点（初始为头节点）

        while (current != null) {
            ListNode temp = current.next; // 保存当前节点的下一个节点（防止断链）
            current.next = pre;           // 反转指针：当前节点指向前驱
            pre = current;                // 前驱后移（成为新的当前节点）
            current = temp;               // 当前节点后移（处理下一个节点）
        }
        return pre; // 循环结束时，pre 是原链表的最后一个节点（即新链表的头节点）
    }

    /**
     * 递归法反转链表
     *
     * @param prev 前驱节点（初始为 null）
     * @param cur  当前节点（初始为头节点）
     * @return 反转后的新链表头节点
     */
    public static ListNode digui(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev; // 终止条件：当前节点为 null 时，prev 是原链表的最后一个节点（新头节点）
        }
        ListNode temp = cur.next; // 保存当前节点的下一个节点
        cur.next = prev;          // 反转指针：当前节点指向前驱
        return digui(cur, temp);  // 递归处理下一个节点（当前节点成为新的前驱）
    }

    // -------------------- 辅助测试方法 --------------------

    /**
     * 根据数组创建链表（方便测试）
     *
     * @param arr 输入数组（如 [1,2,3] 生成 1->2->3）
     * @return 链表头节点
     */
    public static ListNode createList(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        ListNode dummy = new ListNode(); // 虚拟头节点辅助创建
        ListNode current = dummy;
        for (int num : arr) {
            current.next = new ListNode(num);
            current = current.next;
        }
        return dummy.next; // 返回真实头节点
    }

    /**
     * 打印链表内容（方便验证结果）
     *
     * @param head 链表头节点
     * @return 链表字符串（如 "1->2->3" 或 "null"）
     */
    public static String printList(ListNode head) {
        if (head == null) {
            return "null";
        }
        StringBuilder sb = new StringBuilder();
        ListNode current = head;
        while (current != null) {
            sb.append(current.val);
            if (current.next != null) {
                sb.append("->");
            }
            current = current.next;
        }
        return sb.toString();
    }

    // -------------------- 主测试方法 --------------------
    public static void main(String[] args) {
        // 测试 1：空链表反转
        System.out.println("=== 测试 1：空链表 ===");
        ListNode emptyHead = null;
        ListNode reversedEmpty = doublePoint(emptyHead);
        System.out.println("双指针反转结果：" + printList(reversedEmpty)); // 预期：null

        reversedEmpty = digui(null, emptyHead);
        System.out.println("递归反转结果：" + printList(reversedEmpty));   // 预期：null


        // 测试 2：单节点链表反转
        System.out.println("\n=== 测试 2：单节点链表 ===");
        int[] singleArr = {1};
        ListNode singleHead = createList(singleArr);
        System.out.println("原链表：" + printList(singleHead)); // 预期：1

        ListNode reversedSingle = doublePoint(singleHead);
        System.out.println("双指针反转结果：" + printList(reversedSingle)); // 预期：1

        reversedSingle = digui(null, singleHead);
        System.out.println("递归反转结果：" + printList(reversedSingle));   // 预期：1


        // 测试 3：多节点链表反转（1->2->3->4->5）
        System.out.println("\n=== 测试 3：多节点链表 ===");
        int[] multiArr = {1, 2, 3, 4, 5};
        ListNode multiHead = createList(multiArr);
        System.out.println("原链表：" + printList(multiHead)); // 预期：1->2->3->4->5

        // 双指针法反转
        ListNode reversedMultiDouble = doublePoint(multiHead);
        System.out.println("双指针反转结果：" + printList(reversedMultiDouble)); // 预期：5->4->3->2->1

        // 递归法反转（重新创建链表，避免原链表已被修改）
        ListNode multiHead2 = createList(multiArr);
        ListNode reversedMultiDigui = digui(null, multiHead2);
        System.out.println("递归反转结果：" + printList(reversedMultiDigui));   // 预期：5->4->3->2->1
    }
}